1. Field of the Invention
The present invention relates to a technique for encoding and decoding image data.
2. Description of the Related Art
Japanese Patent Laid-Open No. 04-326669 discloses a technique of compressing a multi-valued image where a character/line image and a natural image are mixed. According to this document, an input image is divided by block, as a unit of orthogonal transformation upon encoding, then it is presumed that a most frequent value within each block indicates a character or line image. Then, the pixel data of the mode color information or density information is selected, and extracted from the block. Then lossless encoding such as run-length encoding is performed on the color to be extracted and identification information indicating whether or not it is the pixel to be extracted (Hereinbelow, these two informations will be generally referred to as “resolution information”). Then, respective pixel values of the natural image after the extraction of character/line image information are substituted with a block average value except the pixels extracted as character/line image information. Then, lossy encoding such as JPEG encoding is performed on the substitution-processed natural image.
FIG. 12 shows a 4×4 pixel block data as an example of the above color information extraction. In the pixel block data in FIG. 12, a (part of) a character image at level “240” is overwritten on a part of a natural image in which an average level is “66”. Generally, in a natural image, image information is generated through an analog input device such as a scanner or digital camera, variations occur in pixel values due to noise or the like. On the other hand, in a digitally-generated character image, it can be considered that noise is not mixed and the same value is continued. From this presumption, a mode of the block of interest is detected and extracted as a character/line image from the block. In FIG. 12, as a mode of the pixel block is “240”, this value becomes a color to be extracted. Accordingly, identification information indicating the position of the pixel to be extracted is as shown in FIG. 13. The above-described color to be extracted of the character/line image and the above-described identification information are compressed by lossless encoding.
On the other hand, as an average value of the pixel data for which the above-described identification information is “0” is “66”, the pixel data of the region in which the above-described identification information is “1” is substituted with the above-described average value. FIG. 14 shows the pixel data (gray-level information) after the substitution. The data is compressed by lossy encoding.
Further, a technique of separating a multi-valued image into plural components and independently encoding the components as disclosed in Japanese Patent Laid-Open Nos. 03-254573, 04-040074 and 2002-077631 is known.
When the color of an overwritten character has the same value as in the pixel block in FIG. 12, the technique disclosed in the above Japanese Patent Laid-Open No. 04-326669 is effective for improving the encoding efficiency. However, when a character image having gradation in color (Hereinbelow, referred to as a “gradation character”) is overwritten on a natural image, variations occur in pixel values of character/line image portions. Similarly, variations occur in pixel values when an image including character/line images is obtained by image sensing through an analog input device such as a scanner or digital camera. In this manner, when variations occur in pixel values of character/line images, it is difficult to improve the compressibility.
This problem will be described using FIG. 15 showing a 4×4 block pixel data.
In the pixel data shown in FIG. 15, a character image having values “231”, “233”, “235”, “239” and “240” is overwritten on a part of a natural image in which an average level is “66”. In the conventional art, as a mode having a maximum appearance probability within each block becomes a color to be extracted, the color to be extracted in this example is “65”, and the identification information indicating the pixel position is as shown in FIG. 16. As an average value of the pixel data for which the identification information is “0” is “144”, pixels for which the identification information is “1” are substituted with the average value as shown in FIG. 17 (gray-level information). In the gray-level information, edge components of the pixel data shown in FIG. 15 are almost not eliminated. As a result, the compressibility cannot be improved.
Further, when a histogram within each block is obtained then a threshold value is generated from the histogram and a character portion is extracted, a substitute pixel (a pixel for which the above-described identification information is “1”) is substituted with a color to be extracted upon decoding. Accordingly, in a block having tonality such as a gradation character, the gradation cannot be reproduced without difficulty.